package com.example.graph;

import java.util.*;

/**
 * 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
 * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。
 * 如果没有这样的路线，则输出 -1。
 * <p>
 * 示例 1：
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 1
 * 输出: 200
 * <p>
 * 示例 2：
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 0
 * 输出: 500
 * <p>
 * 提示：
 * <p>
 * n 范围是 [1, 100]，城市标签从 0 到 n - 1
 * 航班数量范围是 [0, n * (n - 1) / 2]
 * 每个航班的格式 (src, dst, price)
 * 每个航班的价格范围是 [1, 10000]
 * k 范围是 [0, n - 1]
 * 航班没有重复，且不存在自环
 */
public class Leetcode787_FindCheapestPrice {
    public static void main(String[] args) {
        int n = 3;
        int[][] flights = {
                {0, 1, 100}, {1, 2, 100}, {0, 2, 500}
        };
        int src = 0;
        int dst = 2;
        int k = 0;
        int cheapestPrice = new Solution().findCheapestPrice(n, flights, src, dst, k);
        System.out.println(cheapestPrice);

//        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
//        minHeap.offer(new int[] {1, 3, 7});
//        minHeap.offer(new int[] {2, 2, 6});
//        minHeap.offer(new int[] {6, 5, 3});
//        minHeap.offer(new int[] {8, 4, 1});
//
//        while (!minHeap.isEmpty()) {
//            int[] tmp = minHeap.poll();
//
//            for (int t : tmp) {
//                System.out.print(t + ",");
//            }
//            System.out.println();
//        }


    }


    static class Solution {
        private boolean[] visited;
        private int res = Integer.MAX_VALUE;
        Map<Integer, List<int[]>> adj = new HashMap<>();

        public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
            return findCheapestPrice3(n, flights, src, dst, k);
        }

        /**
         * 解法一: 暴力法(超时)
         * <p>
         * 深度优先遍历尝试每一种可能的情况
         *
         * @param n
         * @param flights
         * @param src
         * @param dst
         * @param k
         * @return
         */
        public int findCheapestPrice1(int n, int[][] flights, int src, int dst, int k) {

            // 1.首先根据给出的flights构建出邻接表并完成初始化工作
            for (int i = 0; i < flights.length; i++) {
                adj.computeIfAbsent(flights[i][0], key -> new ArrayList<>())
                        .add(new int[]{flights[i][1], flights[i][2]});
            }
            visited = new boolean[n];

            dfsTraverse(src, dst, k + 1, 0);
            return res == Integer.MAX_VALUE ? -1 : res;
        }

        /**
         * 从 src 出发，到 dst 为止，最多经过 k 站（这里 k 包括 src）
         *
         * @param src
         * @param dst
         * @param k    中转站个数(包含src)
         * @param cost 已经花费的价格
         */
        private void dfsTraverse(int src, int dst, int k, int cost) {
            if (src == dst) {
                res = cost;
                return;
            }

            if (k == 0) // 经过了K个中转站没有可达路径，直接返回
                return;

            if (adj.get(src) != null) {
                for (int i = 0; i < adj.get(src).size(); i++) {
                    int[] tmp = adj.get(src).get(i);
                    if (visited[tmp[0]]) // 当前邻接点已经被访问过了
                        continue;
                    if (cost + tmp[1] > res) // 剪枝：跳过可能产生较高费用的路径，从而选出最少价格
                        continue;

                    visited[tmp[0]] = true;
                    dfsTraverse(tmp[0], dst, k - 1, cost + tmp[1]);
                    visited[tmp[0]] = false;

                }
            }
        }

        /**
         * 解法二:迪杰斯特拉算法最小堆方式(超时)
         *
         * @param n
         * @param flights
         * @param src
         * @param dst
         * @param K
         * @return
         */
        public int findCheapestPrice2(int n, int[][] flights, int src, int dst, int K) {
            // 使用邻接矩阵表示有向图，0 表示不连通
            int[][] graph = new int[n][n];
            for (int[] flight : flights) {
                graph[flight[0]][flight[1]] = flight[2];
            }

            Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            // 向集合添加一个记录（起点, 费用, 站数限制）的数组，K + 1 表示可以走过站点的个数
            minHeap.offer(new int[]{src, 0, K + 1});

            while (!minHeap.isEmpty()) {
                int[] front = minHeap.poll();
                int v = front[0];
                int price = front[1];
                int k = front[2];

                if (v == dst) {
                    return price;
                }

                // 如果还可以中转一个站
                if (k > 0) {
                    for (int i = 0; i < n; i++) {
                        // 并且存在一条有向边
                        if (graph[v][i] > 0 ) {
                            // 优先队列中存入：有向边指向的顶点 i、从起点 src 到 i 的总路径长度、还有多少站可以中转
                            minHeap.offer(new int[]{i, price + graph[v][i], k - 1});
                        }
                    }
                }
            }
            return -1;

        }

        /**
         * Bellman-ford 算法
         * Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。
         * 缺点是时间复杂度过高，高达O(VE), V为顶点数，E为边数。
         *
         * 主要思想:
         * 对所有的边进行n-1轮松弛操作(动态规划)，
         * 因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含 n-1 边。
         * 换句话说，第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；（相当于动态规划的初始化状态）
         * 第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；
         * 第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离
         * 第 n-1 轮在对所有的边进行松弛后，得到的是源点最多经过 n-1 条边到达其他顶点的最短距离
         *
         * 实现:
         *   1.原问题与子问题:
         *     求解经过 i 次中转能到达各个节点的最短路径
         *
         *   2.设计状态:
         *     dp[i][j] = m 表示从源节点(src) 中间经过 j 个顶点 到顶点 i 的最短路径为m
         *
         *   3.松弛操作(状态转移方程):
         *
         *   4.边界值:
         *     dp[src][i] = 0(0 <= i < n) 从 src 到 src 不管经过多少次中转最短路径都是0
         *
         * 而对于本题只需要进行 k + 1次松弛操作即可
         * @param n
         * @param flights
         * @param src
         * @param dst
         * @param K
         * @return
         */
        public int findCheapestPrice3(int n, int[][] flights, int src, int dst, int K) {
            int[][] dp = new int[n][K + 1]; // dp[i][j] = m 表示从 源节点(src) 中间经过 j 个顶点 到 i 的最短路径为m
            // 初始化 1：由于找最短路径，因此初始化的时候赋值成为一个不可能的较大的值
            for (int i = 0; i < n; i++) {
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            // 自己到自己，不管经过几个顶点，最短路径都是 0
            for (int i = 0; i <= K; i++) {
                dp[src][i] = 0;
            }

            // 第 1 轮松弛操作，只需要对从 src 出发的边进行松弛操作(初始化)
            for (int[] flight : flights) {
                if (flight[0] == src) {
                    dp[flight[1]][0] = flight[2];
                }
            }

            // 第 2 轮到第 K + 1 轮松弛操作，最后一轮松弛操作是为了检测是否可达
            for (int i = 1; i <= K; i++) {
                for (int[] flight : flights) {
                    int from = flight[0];
                    int to = flight[1];
                    // 每一次松弛操作的结果是互相独立的，因此只有在上一轮（第 i - 1 轮）得到单源最短路径的顶点，才需要执行松弛操作
                    if (dp[from][i - 1] != Integer.MAX_VALUE) {
                        dp[to][i] = Math.min(dp[from][i - 1] + flight[2], dp[to][i]);
                    }
                }
            }

            // 如果不可达，返回 -1
            if (dp[dst][K] == Integer.MAX_VALUE) {
                return -1;
            }
            return dp[dst][K];
        }
    }
}
